package cn.arnold.linkedlist;

public class CircleSingleLinkedList {

    // 创建first节点
    private Boy first = null;

    /**
     * 根据序号添加boy节点，形成环形
     *
     * @param nums：节点数量
     */
    public void addBoys(int nums) {
        // 传参校验
        if (nums < 1) {
            System.out.println("传入的参数不正确");
            return;
        }
        // 辅助指针
        Boy curBoy = null;
        // 循环添加Boy，根据编号顺序形成环形
        for (int i = 1; i <= nums; i++) {
            // 根据编号创建boy节点
            Boy boy = new Boy(i);
            // 如果是第一个节点
            if (i == 1) {
                first = boy;
                first.setNext(first); // 形成环
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first); // 形成环
                curBoy = boy;
            }
        }
    }

    /**
     * 遍历链表
     */
    public void showList() {
        // 判断链表是否为空
        if (first == null) {
            System.out.println("链表为空...");
            return;
        }
        // 辅助指针
        Boy temp = first;
        while (true) {
            System.out.println("小孩的编号为：" + temp.getNo());
            if (temp.getNext() == first) { //终止条件
                break;
            }
            // temp后移
            temp = temp.getNext();
        }
    }

    /**
     * 约瑟夫问题：小孩出圈
     *
     * @param startNo：起始编号
     * @param coutNum：数几下
     * @param totalNums：总数
     */
    public void JosephuBoy(int startNo, int coutNum, int totalNums) {
        // 参数校验
        if (first == null || startNo < 1 || startNo > totalNums) {
            System.out.println("参数传递不合理...");
            return;
        }
        // 辅助指针：指向环形链表的最后一个节点（跟在first节点的后面）
        Boy firstBehind = first;
        while (true) {
            if (firstBehind.getNext() == first) { // 指向环形链表的最后一个节点
                break;
            }
            firstBehind = firstBehind.getNext();
        }
        // 报数前：first和firstBehind同时向前移动startNo-1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            firstBehind = firstBehind.getNext();
        }
        // 报数时：first和firstBehind同时向前移动coutNum-1次，此时first指针指向的节点就是要出圈的节点
        while (true) {
            if (firstBehind == first) {    //只有一个节点
                break;
            }
            // first和firstBehind同时向前移动coutNum-1次
            for (int i = 0; i < coutNum - 1; i++) {
                first = first.getNext();
                firstBehind = firstBehind.getNext();
            }
            // 此时first指针指向的节点就是要出圈的节点:删除节点
            System.out.println("出圈小孩序号：" + first.getNo());
            first = first.getNext();
            firstBehind.setNext(first);
        }
        System.out.println("最后留在圈中的小孩：" + first.getNo());
    }
}
